#include <vector>
#include <string>
using namespace std;
class Solution
{
public:
    bool is_part(const string &s, int start, int end)
    {
        for (int i = start, j = end - 1; i <= j; i++, j--)
            if (s[i] != s[j])
                return false;
        return true;
    }
    int minCut(string s)
    {
        int size(s.size());
        vector<vector<bool>> vt(size, vector<bool>(size));
        for (int len = 1; len <= size; len++)
            for (int i = 0; i + len <= size; i++)
                if (is_part(s, i, i + len))
                    vt[i][i + len - 1] = 1;
        vector<int> res(size, INT_MAX);
        res[0] = 0;
        // 往前找有没有位置与这个新字符构成回文
        // 然后就只用从这个位置之前加一刀即可 res[j-1]+1
        for (int i = 1; i < size; i++)
        {
            if (vt[0][i])
                res[i] = 0;
            for (int j = 1; j <= i; j++)
            {
                if (vt[j][i])
                    res[i] = min(res[i], res[j - 1] + 1);
            }
        }
        return res.back();
    }
};